10166. Max-куча

Задан массив целых чисел. Переставьте его элементы так чтобы получилась max-куча.

Вход. Первая строка содержит количество элементов массива n (n ≤ 1000). Вторая строка содержит n целых чисел.

Выход. Выведите массив, который является max-кучей.

Пример входа	Пример выхода
6 5 3 2 7 1 10	10 7 5 3 1 2

РЕШЕНИЕ

куча

Анализ алгоритма

Прочитаем входные данные в массив а. Для всех индексов массива от n / 2 до 1 выполняем процедуру heapify. Массив превращается в max-кучу.

Пример

Исходный массив и конечный, являющийся кучей, представлены ниже.

Реализация алгоритма

Объявим массив, который в дальнейшем будет преобразован в кучу.

#define MAX 1001

int a[MAX];

Функция left возвращает индекс левого сына.

int left(int i)

{

return 2 * i;

}

Функция right возвращает индекс правого сына.

int right(int i)

{

return 2 * i + 1;

}

Функция swap меняет местами элементы i и j.

void swap(int &i, int &j)

{

int temp = i; i = j; j = temp;

}

Функция heapify восстанавливает свойство кучи для дерева с корнем в i-ой вершине. Третий параметр n – размер поддерживаемой кучи.

void heapify(int a[], int i, int n)

{

int largest = 0;

int l = left(i);

int r = right(i);

Ищем индекс максимального элемента среди текущего a[i] и его сыновей a[l] и a[r].

if (l <= n && a[l] > a[i]) largest = l;

else largest = i;

if (r <= n && a[r] > a[largest]) largest = r;

Если a[i] не является максимальным элементом, то меняем его с максимальным и далее рекурсивно восстанавливаем свойство кучи в левом или правом поддереве.

if (largest != i)

{

swap(a[i], a[largest]);

heapify(a, largest, n);

}

}

Основная часть программы. Читаем входной массив, начиная с индекса 1.

scanf("%d", &n);

for (i = 1; i <= n; i++)

scanf("%d", &a[i]);

Для всех индексов от n / 2 до 1 выполняем процедуру heapify.

for (i = n / 2; i > 0; i--)

heapify(a, i, n);

Выводим результирующий массив, который является max-кучей.

for (i = 1; i <= n; i++)

printf("%d ", a[i]);

printf("\n");

Java реализация

import java.util.*;

public class Main

{

static int left(int i)

{

return 2 * i;

}

static int right(int i)

{

return 2 * i + 1;

}

static void swap(int a[], int i, int j)

{

int temp = a[i]; a[i] = a[j]; a[j] = temp;

}

//max - heap

static void heapify(int a[], int i, int n) // n = size of a heap

{

int largest = 0;

int l = left(i);

int r = right(i);

if (l <= n && a[l] > a[i]) largest = l;

else largest = i;

if (r <= n && a[r] > a[largest]) largest = r;

if (largest != i)

{

swap(a, i, largest);

heapify(a, largest, n);

}

}

public static void main(String[] args) {

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m[] = new int[n+1];

for(int i = 1; i <= n; i++)

m[i] = con.nextInt();

for(int i = n / 2; i > 0; i--)

heapify(m,i,n);

for(int i = 1; i <= n; i++)

System.out.print(m[i] + " ");

System.out.println();

con.close();

}

}